lib/Mi manual de algoritmos/version_maraton_nacional_2008/src/number_theory/bigmod.cpp

   1 //retorna (b^p)mod(m)
   2 // 0 <= b,p <= 2147483647
   3 // 1 <= m <= 46340
   4 long f(long b, long p, long m){
   5   long mask = 1;
   6   long pow2 = b % m;
   7   long r = 1;
   8
   9   while (mask){
  10     if (p & mask)
  11       r = (r * pow2) % m;
  12     pow2 = (pow2*pow2) % m;
  13     mask <<= 1;
  14   }
  15   return r;
  16 }